// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

func main() {
	// 测试用例
	board := [][]byte{
		{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
		{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
		{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
		{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
		{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
		{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
		{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
		{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
		{'.', '.', '.', '.', '8', '.', '.', '7', '9'},
	}

	fmt.Println("初始板：")
	for _, row := range board {
		fmt.Println(string(row))
	}

	if SolveSudoku(board) {
		fmt.Println("\n找到的解决方案：")
		for _, row := range board {
			fmt.Println(string(row))
		}
	} else {
		fmt.Println("\n未找到解决方案")
	}
}

// 为数独板单元定义结构体
type Cell struct {
	row, col int
}

// 递归地解决给定的数独板
// 如果板可解决，则返回 true，否则返回 false
func SolveSudoku(board [][]byte) bool {
	//遍历板上的所有单元格
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			// 如果单元格为空
			if board[i][j] == '.' {
				// 则尝试单元格的所有可能值
				for c := '1'; c <= '9'; c++ {
					//如果该值有效，则设置它并继续求解
					if IsValid(board, i, j, byte(c)) {
						board[i][j] = byte(c)
						if SolveSudoku(board) {
							return true
						} else {
							board[i][j] = '.'
						}
					}
				}
				//如果所有值都不起作用，则回溯
				return false
			}
		}
	}
	return true
}

// 检查给定值对于面板中的单元格是否有效
// 如果该值有效，则返回 true，否则返回 false
func IsValid(board [][]byte, row int, col int, c byte) bool {
	//检查值是否出现在同一行、列或子框中
	for i := 0; i < 9; i++ {
		if board[i][col] == c {
			return false
		}
		if board[row][i] == c {
			return false
		}
		if board[3*(row/3)+i/3][3*(col/3)+i%3] == c {
			return false
		}
	}
	return true
}

//$ go run sudokuSolver.go
//初始板：
//53..7....
//6..195...
//.98....6.
//8...6...3
//4..8.3..1
//7...2...6
//.6....28.
//...419..5
//....8..79
//
//找到的解决方案：
//534678912
//672195348
//198342567
//859761423
//426853791
//713924856
//961537284
//287419635
//345286179
